/* 
    779. 第K个语法符号
*/
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function (n, k) {
	if (n === 1) return 0
	// 计算当前行的长度
	let length = 2 ** (n - 1)
	// 如果K大于长度的一半，就是k所在位置是后半段
	if (k > length / 2) {
		// 先得到上一行的值，位置是k相对于后半段的位置
		var val = kthGrammar(n - 1, k - length / 2)
		// 然后把值反过来
		return val === 0 ? 1 : 0
	} else {
		// 值就是上一行K位置的值
		return kthGrammar(n - 1, k)
	}
}
const res = kthGrammar(4, 2)
console.log('kthGrammar :>>', res)
